package mao.leetcode.others;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class leetcode207 {

    public static boolean canFinish_1(int numCourses, int[][] prerequisites) {
        int[] inDegrees = new int[numCourses];
       for(int[] pre :prerequisites) inDegrees[pre[0]]++;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0)
                queue.offer(i);
        }
       while ( !queue.isEmpty()){
           Integer preNode = queue.poll();
           numCourses--;
           for (int[] pre : prerequisites){
               if (pre[1] == preNode){
                   inDegrees[pre[0]]--;
                   if (inDegrees[pre[0]] == 0)
                       queue.offer(pre[0]);
               }
           }
       }
       return numCourses==0;
    }


    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int flags[] = new int[numCourses];
        for (int i = 0; i < flags.length; i++) {
            flags[i] = 0 ;
        }
        for(int[] p : prerequisites){
            if ( ! dfs(p[1],flags,prerequisites)){
                return false;
            }
        }
        return true;
    }
    private static List res = new ArrayList();
    public static boolean dfs(int courseNum,int[] flags,int[][] pre){
        if (flags[courseNum] == -1) return true;
        if (flags[courseNum] == 1) return false;
        flags[courseNum] = 1;

        for(int[] p : pre){
            if (p[1] == courseNum){
                if ( dfs(p[0],flags,pre)== false)
                    return false;
            }
        }
        flags[courseNum] = -1;
        res.add(courseNum);
        return true;
    }

    public static void main(String[] args) {
        int[][] prerequisites = {{0,1}};
        boolean can = canFinish(2,prerequisites);
        System.out.println(can);
    }
}
